Point Cloud

A sample

Learn Topological and Geometric Features

A Reconstruction

  • The topology is the wedge of two circles (two 11-dimensional cycles)
  • The geometry is graph-like

Good Shapes

Circle

Donut
  • Abstract Riemannian manifolds
  • Submanifolds of ℝN\mathbb{R}^N

Bad Shapes

Source: Kyoto City Official Traval Guide

A Real Application

The City of Berlin

Q: How to draw the map of the city from a noisy point-cloud of GPS locations?

A Reconstruction of Berlin

Source: mapconstruction.org

Reconstruction Goals

  • Goal: Infer the topology of XX from SS.

    • Estimate only the Betti numbers—number of connected components, cycles, voids, etc—of XX

    • construct a topological space X̂\widehat{X} from SS to retain the topology of XX in some appropriate sense

      • homotopy equivalent
      • homeomorphic
      • geometrically close (in Hausdorff distance)

My Motivation

  • Provide a window of scales for the Vietoris–Rips complexes for a topologically-faithful reconstruction
  • Design provable reconstruction algorithms particularly for bad shapes
  • Topological perspective on Manifold and graph hypotheses for random data
    • Geometric Whitney’s Theorem by Fefferman et al.
  • Understand the topology of ℛβ(X)\mathcal{R}_\beta(X) and their shadow
  • When is the homology of ℛβ(X)\mathcal{R}_\beta(X) (and their shadow) finitely generated?

The Vietoris–Rips Complexes

  • a metric space (X,dX)(X,d_X)

  • a scale β>0\beta>0

  • ℛβ(X)\mathcal{R}_\beta(X) is an abstract simplicial complex

    • XX is the vertex set
    • each subset A⊂XA\subset X of (k+1)(k+1) points with diameter less than β\beta is a kk-simplex.

Gromov’s Perspective

—Metric structures of Riemann & non-Riemann Spaces, page100

Let XX be a length metric space…given by ε\varepsilon-nets Xε0X_\varepsilon^{0} in XX which Hausdorff converges XX…

…One can turn such a space into a path metric space, namely a graph Xε1⊂XX_\varepsilon^{1}\subset X with Xε0X_\varepsilon^{0} as its vertex set, and where two points xx and yy in Xε1X_\varepsilon^{1} within distance δ≤δε\delta\leq\delta_\varepsilon joined by an edge of length δ\delta.

…fll in the small triangles of edges in the graph Xε1X_\varepsilon^{1} by actual 22-dimensional triangles to obtain Xε2⊂XX_\varepsilon^{2}\subset X, then π1(Xε2)=π1(X)\pi_1(X_\varepsilon^{2})=\pi_1(X) for ε,δε→0\varepsilon,\delta_\varepsilon\to0 with ε/δε→∞\varepsilon/\delta_\varepsilon\to\infty.

Hausmann’s Theorem

Hausmann (1995)

For any closed Riemannian manifold MM and 0<β<ρ(M)0<\beta<\rho(M), the Vietoris–Rips complex ℛβ(M)\mathcal{R}_\beta(M) is homotopy equivalent to MM.

  • Convexity Radius: ρ(M)\rho(M) is the largest (sup) radius so that geodesic balls are convex.
    • ρ(S1)=π2\rho(S^1)=\frac{\pi}{2}
    • ρ(M)>0\rho(M)>0 for a compact manifold
  • Hausmann constructed a homotopy equivalence T:ℛβ(M)→MT:\mathcal{R}_{\beta}(M)\to M
  • Since MM has finitely generated homology, so does ℛβ(M)\mathcal{R}_{\beta}(M)
  • vertex set is the entire manifold MM!

Finite Reconstruction Problem

Hausmann’s Curious Question

What about the Vietoris–Rips complex of a finite, dense subset S⊂MS\subset M?

  • Manifold reconstruction from a dense sample
  • More generally, a metric space (S,dS)(S,d_S) close to MM in the Gromov-Hausdorff distance.

Gromov–Hausdorff Distance:

  • similarity measure between abstract metric spaces (X,dX)(X,d_X) and (Y,dY)(Y,d_Y)
  • Definition: dGH(X,Y)=infdHZ(f(X),g(Y))d_{GH(X,Y)}=\inf d_H^Z(f(X),g(Y))
    • inf over metric spaces (Z,dZ)(Z,d_Z) and isometries f:X→Zf:X\to Z, g:Y→Zg:Y\to Z

Latschev’s Remarkable Solution

Latschev (2001)

Every closed Riemannian manifold MM has an ϵ0>0\epsilon_0>0 such that for any 0<β≤ϵ00<\beta\leq\epsilon_0 there exists some δ>0\delta>0 so that for any sample SS: dGH(S,M)≤δ⟹ℛβ(S)≃M. d_{GH}(S,M)\leq\delta\implies \mathcal R_\beta(S)\simeq M.

  • the threshold ϵ0=ϵ0(M)\epsilon_0=\epsilon_0(M) depends solely on the geometry of MM. But the theorem did not say how!

  • δ=δ(β)\delta=\delta(\beta) is a function (a fraction in practice) of β\beta.

  • The result is qualitative

    • it’s unavoidable (uses Lebesgue’s number lemma)

  • Nonetheless, the result provides a promising answer to Hausmann’s question, and more!

Quantitative Latschev’s Theorem

Metric Graph Reconstruction [J. Appl. & Comp. Top., Majhi (2023)]

Let (G,dG)(G,d_G) be a compact, path-connected metric graph, (S,dS)(S,d_S) a metric space, and β>0\beta>0 a number such that 3dGH(G,S)<β<34ρ(G).3d_{GH}(G,S)<\beta<\frac{3}{4}\rho(G). Then, ℛβ(S)≃G\mathcal R_\beta(S)\simeq G.

  • The result is quantitative

    • ϵ0=34ρ(G)\epsilon_0=\frac{3}{4}\rho(G)

    • δ=13β\delta=\frac{1}{3}\beta

  • The constants are not optimal!

    • Optimal ϵ0=23ρ(G)\epsilon_0=\frac{2}{3}\rho(G).

Quantitative Latschev’s Theorem

Riemannian Manifold Reconstruction [SoCG’24, DCG, Majhi (2024)]

Let MM be a closed, connected Riemannian manifold. Let (S,dS)(S,d_S) be a compact metric space and β>0\beta>0 a number such that 1ξdGH(M,S)<β<11+2ξmin{ρ(M),π4κ} \frac{1}{\xi}d_{GH}(M,S)<\beta<\frac{1}{1+2\xi}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\} for some 0<ξ≤1/140<\xi\leq1/14. Then, ℛβ(S)≃M\mathcal R_\beta(S)\simeq M.

  • κ\kappa is an upper bound on the sectional curvatures of MM

  • For ξ=114\xi=\frac{1}{14}:

    • ϵ0=78min{ρ(M),π4κ}\epsilon_0=\frac{7}{8}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\}

    • δ=β14\delta=\frac{\beta}{14}

Quantitative Latschev’s Theorem

Euclidean Submanifold Reconstruction (Majhi 2024)

Let M⊂ℝNM\subset\mathbb R^N be a closed, connected submanifold. Let S⊂ℝNS\subset\mathbb R^N be a compact subset and β>0\beta>0 a number such that 1ξdH(M,S)<β<3(1+2ξ)(1−14ξ)8(1−2ξ)2τ(M) \frac{1}{\xi}d_{H}(M,S)<\beta<\frac{3(1+2\xi)(1-14\xi)}{8(1-2\xi)^2}\tau(M) for some 0<ξ<1/140<\xi<1/14. Then, ℛβ(S)≃M\mathcal R_\beta(S)\simeq M.

  • τ(M)\tau(M) is the reach of MM

  • For ξ=128\xi=\frac{1}{28}:

    • ϵ0=3151352τ(M)\epsilon_0=\frac{315}{1352}\tau(M)

    • δ=β28\delta=\frac{\beta}{28}

Reach

Challenges

  • Bad shapes are ubiquitous in applications
    • manifolds with boundary or not a topological manifold
    • stratefied manifolds
    • Euclidean subsets with vanishing reach (due to corners)
  • A single Rips complex fails to be topologically faithful, no matter the sample density

Metric Spaces of Curvature ≤κ\leq\kappa

  • Length space: A metric space with an instrinsic metric

  • Geodesically complete: a pair can be joined by a length-minimizing path

  • geodesic triangles are “slimmer” than corresponding “model triangles” in a standard space of constant curvature κ\kappa.

  • Examples:

    • Closed Riemannian manifolds
    • Submanifolds of ℝN\mathbb{R}^N
    • stratefied manifolds
    • metric graphs
    • embedded graphs in ℝN\mathbb{R}^N
    • Euclidean Polytopes

  • Quantitative Lastchev’s Theorem for CAT(κ)\mathrm{CAT}(\kappa) Spaces (Komendarczyk, Majhi, and Tran 2024)

Euclidean Subset Reconstruction

  • The sample SS comes equipped with ∥⋅∥\|\cdot\|
  • Euclidean Vietoric–Rips ℛβ(S)\mathcal{R}_\beta(S) fails almost aways for any scale β\beta
  • Remedy?

ε\varepsilon-path Metric:

  • Fix an ε>0\varepsilon>0, proportional to dH(S,X)d_H(S,X)

  • For any two sample points a,b∈Sa,b\in S, define dSε(a,b)d_S^\varepsilon(a,b) to be the shortest distance when hopping over the points of SS with a step size ≤ε\leq\varepsilon.

ε\varepsilon-path Metric on SS
  • For a dense enough sample SS of XX, dSεd^\varepsilon_S is quasi-isometric to the length metric on XX
  • Consider the Vietoris–Rips of SS under dεd_\varepsilon; call it ℛβε(S)\mathcal{R}_\beta^\varepsilon(S)

Large-scale Distortion

  • A finite sample around a corner does not see the corner
  • Global distortion: δ(X)=supa≠bdXL(a,b)∥a−b∥\delta(X)=\sup_{a\neq b}\frac{d^L_X(a,b)}{\|a-b\|}
  • Large-scale distortion: δRε(X)=supdL(a,b)≥RdXL(a,b)dXεL(a,b)\delta^\varepsilon_R(X)=\sup_{d^L(a,b)\geq R}\frac{d^L_X(a,b)}{d^L_{X^\varepsilon}(a,b)}
  • δRε(X)→1\delta^\varepsilon_R(X)\to1 as ε→0\varepsilon\to0, provided XX is a compact length space

Euclidean Subsets (Komendarczyk, Majhi, and Tran 2024)

Let XX be a geodesic subspace of ℝN\mathbb R^N. Let ξ∈(0,1)\xi\in\left(0,1\right) and β>0\beta>0 be fixed numbers. 0<ε≤β0<\varepsilon\leq\beta such that δβε(X)≤1+(ξ1+ξ)\delta^\varepsilon_{\beta}(X)\leq1+\left(\frac{\xi}{1+\xi}\right), then for any compact subset S⊂ℝNS\subset\mathbb R^N with dH(X,S)<12ξεd_H(X,S)<\frac{1}{2}\xi\varepsilon, we have ℛβε(S)≃X\mathcal{R}_\beta^\varepsilon(S)\simeq X.

Back to Gromov: Vietoris–Rips Shadow

  • Vietoris–Rips complexes are abstact, hence contain only topological information
  • Geometric reconstruction: entails constructing X̂⊂ℝN\widehat{X}\subset\mathbb R^N from samples so that X̂≃X\widehat{X}\simeq X and dH(X̂,X)d_H(\widehat{X}, X) is controlled.
  • A good candidate for X̂\widehat{X} is the shadow of a topologically-faithful Vietoris–Rips.
  • Shadow: For simplicial complex 𝒦\mathcal K with vertices from ℝN\mathbb R^N is the union of the (Euclidean) convex hulls of simpices σ∈𝒦\sigma\in\mathcal K
    • Chambers et al. (2010); Adamaszek, Frick, and Vakili (2017)

Graph Reconstruction via Shadow

Geometric Reconstruction (Komendarczyk, Majhi, and Mitra 2025)

Let G⊂ℝ2G \subset \mathbb{R}^2 a graph. Fix any ξ∈(0,1−Θ6)\xi\in\left(0,\frac{1-\Theta}{6}\right). For any positive β<min{Δ(G),ℓ(G)12}\beta<\min\left\{\Delta(G),\frac{\ell(G)}{12}\right\}, choose a positive ε≤(1−Θ)(1−Θ−6ξ)12β\varepsilon\leq\frac{(1-\Theta)(1-\Theta-6\xi)}{12}\beta such that δβε(G)≤1+2ξ1+ξ\delta^{\varepsilon}_{\beta}(G)\leq\frac{1+2\xi}{1+\xi}. If S⊂ℝ2S\subset \mathbb R^2 is compact and dH(G,S)<12ξεd_H(G,S)<\tfrac{1}{2}\xi\varepsilon, then the shadow sh(ℛβε(S))sh(\mathcal R_\beta^\varepsilon(S)) is homotopy equivalent to GG. Moreover, dH(sh(ℛβε(S)),G)<(β+12ξε)d_H(sh(\mathcal R_\beta^\varepsilon(S)),G)<\left(\beta+\frac{1}{2}\xi\varepsilon\right).

  • Θ∈(0,1)\Theta\in(0,1): depends on the angles between tangents of edges at the graph vertices
  • Δ(G)\Delta(G): Shadow radius positive number for graphs with smooth edges